%%%-------------------------------------------------------------------
%%% File    : p41.erl
%%% Author  : Plamen Dragozov <plamen at dragozov.com>
%%% Description : 
%%% We shall say that an n-digit number is pandigital if it makes use 
%%% of all the digits 1 to n exactly once. For example, 2143 is a 
%%% 4-digit pandigital and is also prime.
%%%
%%% What is the largest n-digit pandigital prime that exists?
%%%
%%%
%%% Created : 30 Dec 2008
%%%-------------------------------------------------------------------
-module(p41).

%% API
-compile(export_all).

%%====================================================================
%% API
%%====================================================================
%%--------------------------------------------------------------------
%% Function:  solution(Max) -> N.
%% Description: Find the largest pandigital prime number with Max (< 10)or less digits.
%%--------------------------------------------------------------------
solution(Max) ->
    Filter = fun(L) -> 
                     Last = lists:last(L),
                     Prime = Last =/= 5 andalso Last rem 2 =/= 0 andalso is_prime(to_number(L)),
                     {Prime, not Prime}
             end,
    Fun = fun(L, Acc) ->
                   [L|Acc]
          end,    
    [H|_] = for_combinations(Fun, Filter, 0, array:from_list(lists:seq(1,Max)), Max, fac(Max), []),
    to_number(H).  
                     
%Iterate through all possible pandigital numbers of a set of digits filtering them with the Filter function
% and applying the Fun function
% Filter takes the number and should return a tuple {Use, Continue}, positive Use means apply the function
% negative Continue means break and return the result.
%Fun takes the number and the current value of the accumulator and returns the next value for the accumulator.
for_combinations(_, _, 1, _, 1, 1, Acc) -> Acc;%This was the last
for_combinations(Fun, Filter, MaxN, Array, Size, MaxN, Acc) -> % restart combinations of smaller size
    NewArray = array:foldl(fun(Index, Val, FAcc) -> %remove the last element
                                   case Index + 1 of 
                                       Size -> FAcc;
                                       _ -> array:set(Index, Val, FAcc)
                                   end
                           end,
                           array:new(Size - 1),
                           Array),
    for_combinations(Fun, Filter, 0, NewArray, Size - 1, MaxN div Size, Acc);
for_combinations(Fun, Filter, N, Array, Size, MaxN, Acc) ->
    Comb = nth_combination(N, Array, Size, MaxN, []),
    case Filter(Comb) of
        {true, true} -> % use and continue
            for_combinations(Fun, Filter, N + 1, Array, Size, MaxN, Fun(Comb, Acc));
        {true, false} -> % use but break after
            Fun(Comb, Acc);
        {false, true} -> % skip, but continue
            for_combinations(Fun, Filter, N + 1, Array, Size, MaxN, Acc);
        _  -> %skip and break
            Acc
    end.
    
%Return the N-th combination of a set of digits (stored in an array).
nth_combination(_, _, 0, _, Acc) -> lists:reverse(Acc);
nth_combination(N, Array, Size, MaxN, Acc) ->
    NewMaxN = MaxN div Size,
    I = Size - 1 -(N div NewMaxN),
    NewArray = array:foldr(fun(Index, X, Acc1) ->
                                   case true of
                                       true when Index =:= I ->
                                           Acc1;
                                       true when Index < I -> array:set(Index, X, Acc1);
                                       _ -> array:set(Index - 1, X, Acc1)
                                   end
                           end,
                           array:new(Size - 1),
                           Array),
    nth_combination(N rem NewMaxN, NewArray, Size - 1, NewMaxN, [array:get(I, Array)|Acc]).

%%====================================================================
%% Internal functions
%%====================================================================
%factorial of N = N!
fac(N) ->
    fac(N, 1).

fac(0, Acc) -> Acc;
fac(N, Acc) ->
    fac(N-1, Acc*N).

%convert a list of digits to a number
to_number(L) ->
    to_number(L, 0).

to_number([], Acc) -> Acc;
to_number([H|T], Acc) -> to_number(T, Acc*10 + H).


%check if a number is prime (kinda lazy, but good enough)
is_prime(X) ->
    X rem 2 =/= 0 andalso is_prime(X, 3, math:sqrt(X)).
is_prime(_, I, Sqrt) when I > Sqrt ->
    true;
is_prime(X, I, Sqrt) ->
    case X rem I  of
        0 ->
            false;
        _ -> is_prime(X, I + 2, Sqrt)
    end.
